import heapq
import itertools


class WallePriorityQueue:
    def __init__(self):
        self.pq = []
        self.entry_map = {}
        self.REMOVED = '<removed_task>'
        self.counter = itertools.count()

    def size(self):
        return len(self.pq);

    def add_task(self, task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in self.entry_map:
            self.remove_task(task)
        count = next(self.counter)
        entry = [priority, count, task]
        self.entry_map[task] = entry
        heapq.heappush(self.pq, entry)

    def remove_task(self, task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self.entry_map.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            priority, count, task = heapq.heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_map[task]
                return task
        return None


if __name__ == "__main__":
    pq = WallePriorityQueue()
    pq.add_task("job 1 with priority 3", 3)
    pq.add_task("job 2 with priority 10", 10)
    pq.add_task("job 3 with priority 7", 7)
    pq.add_task("job 4 with priority 12", 12)
    pq.add_task("job 5 with priority 1", 1)
    pq.add_task("job 6 with priority 7", 7)
    pq.remove_task("job 2 with priority 10")
    while True:
        t = pq.pop_task()
        if t is not None:
            print(t)
        else:
            break
